package com.algorithm5;

import java.util.Arrays;

public class HeapSort {

    public static void heapSort(int[] array){
        buildHeap(array,array.length-1);
        int j = array.length-1;
        while(j>0){
            swap(array,j,1);
            j--;
            heapify(array,j,1);
        }
    }

    public static void buildHeap(int[] array,int len){
        for(int i=len/2;i>0;i--){
            heapify(array,len,i);
        }
        System.out.println("heapify结果:" + Arrays.toString(array));
    }

    public static void heapify(int[] array,int len,int k){
        int maxP = k;
        int left = 2*k;
        int right = 2*k+1;
        if(left<len && array[left]>array[maxP]){
            maxP = left;
        }
        if(right<len && array[right]>array[maxP]){
            maxP = right;
        }
        if(maxP!=k){
            swap(array,maxP,k);
            heapify(array,len,maxP);
        }



    }
    public static void swap(int[] array,int i,int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }


    public static void main(String[] args){
        int[] array = new int[]{0,8, 9, 3,10, 2, 4, 5, 6, 7, 1};
      /*  buildHeap(array,array.length-1);
        System.out.println("result:"+ Arrays.toString(array));*/
        heapSort(array);
        System.out.println("result:"+ Arrays.toString(array));
    }
}
